package com.dh.leetcode.k1;

import org.junit.Test;

/**
 * @ClassName: _1030_Matrix_cells_in_distance_order
 * @Description: 1030. 距离顺序排列矩阵单元格
 * <p>
 * https://leetcode-cn.com/problems/matrix-cells-in-distance-order/
 * @Author: shouzimu
 * @Date: 2020/11/17 9:25
 */
public class _1030_Matrix_cells_in_distance_order {

    /**
     * 00 01 02
     * 10 11 12
     * <p>
     * |r1 - r2| + |c1 - c2|
     * <p>
     * 从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
     *
     * @param R
     * @param C
     * @param r0
     * @param c0
     * @return
     */
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int len = R * C;
        int[][] matrix = new int[len][2];
        //init
        int cnum = 0;
        for (int i = 0; i < matrix.length; i++) {
            int[] cell = matrix[i];
            cell[0] = cnum;
            cell[1] = i % C;
            if ((i + 1) % C == 0) {
                cnum++;
            }
        }

        //sort
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                int L1 = Math.abs(matrix[j][0] - r0) + Math.abs(matrix[j][1] - c0);
                int L2 = Math.abs(matrix[j + 1][0] - r0) + Math.abs(matrix[j + 1][1] - c0);
                if (L1 > L2) {
                    int[] swap = matrix[j];
                    matrix[j] = matrix[j + 1];
                    matrix[j + 1] = swap;
                }
            }
        }
        return matrix;
    }

    @Test
    public void allCellsDistOrderTest() {
        int[][] matrix = allCellsDistOrder(2, 3, 1, 2);
        for (int i = 0; i < matrix.length; i++) {
            int[] cell = matrix[i];
            System.out.print("[");
            for (int j = 0; j < cell.length; j++) {
                System.out.print(cell[j]);
            }
            System.out.print("],");
        }
    }
}
